package course.p4_list.s4_CycleList;

/**
 * 单向循环链表实现
 */
public class CycleList {

    /**
     * 以输入节点为头，计算出链表长度
     * @param head 任意节点
     * @return 链表长度
     */
    static int ListLength(Node head) {
        int length = 0;
        Node cur = head;
        if(cur==null) return length;
        //先把第一个节点设置为头节点
        cur.isHead = true;
        length++;
        cur = cur.next;
        while (!cur.isHead) {
            length++;
            cur = cur.next;
        }
        // 还原
        head.isHead = false;
        return length;
    }

    /**
     * 遍历打印链表内容
     * @param headNode 链表头节点
     */
    static void toString(Node headNode) {
        Node check = headNode;
        int size = ListLength(headNode);
        if(check==null){
            System.out.print("null");
            return;
        }
        for(int i=0; i < size+1; i++){
            System.out.print(check.nodeName+"->");
            check = check.next;
        }
    }

    /**
     * 此方法用于获得链表的最后一个节点
     * @param head 头节点
     * @return 循环链表的最后一个节点
     */
    static Node getLastNode(Node head) {
        Node cur = head;
        Node pre = head;
        if(cur==null) return null;
        cur.isHead = true;
        cur = cur.next;
        while (cur!=null&&!cur.isHead){
            pre = cur;
            cur = cur.next;
        }
        head.isHead = false;
        return pre;
    }

    /**
     * 主要思路是：
     *      先判断链表中存不存在position位置，若没有输出错误信息并返回头节点；
     *      若存在则进行插入操作：首先判断position是不是为1，因为这种情况不同于其他的。
     *      否则，先找到第position-1个节点和position个节点，将前一个节点的下一节点设为nodeToInsert
     *      将nodeToInsert的下一个节点设置为position节点，这样完成插入操作
     * @param headNode 链表头节点
     * @param nodeToInsert 要插入的节点
     * @param position 指定插入的位置
     * @return 插入后的链表头节点
     */
    static Node Insert(Node headNode, Node nodeToInsert, int position ) {
        if(headNode == null) {
            return nodeToInsert;
        }
        //获得输入链表的长度
        int size = ListLength(headNode);
        //判断链表内是否存在此位置
        if(position>size || position<0) {
            System.out.println("Position of node to insert is invalid.The valid inputs are 0 to"+(size));
            return headNode;
        }
        //获取尾节点
        Node lastNode = getLastNode(headNode);
        //在链表开头插入
        if(position == 0) {
            nodeToInsert.next = headNode;
            //让尾节点指向该节点
            if(lastNode!=null)
                lastNode.next = nodeToInsert;
            return nodeToInsert;
        }
        //在末尾插入
        else if(position == size) {
            //插入操作
            nodeToInsert.next = headNode;
            if(lastNode!=null)
                lastNode.next = nodeToInsert;
        }
        //在中间插入
        else {
            Node pre = headNode;
            int count = 0;
            //找到那个位置的前一个节点
            while(count < position-1) {
                //获得第position-1位置的节点
                pre = pre.next;
                count++;
            }
            //获得第position位置的节点
            Node currentNode = pre.next;
            //插入操作
            nodeToInsert.next = currentNode;
            pre.next = nodeToInsert;
        }
        return headNode;
    }

    /**
     * 方法和前面的插入方法有异曲同工之妙：
     *  主要思想是找到position的前一个节点和后一个节点，然后将他们连接
     * @param headNode 头节点
     * @param position 删除的位置
     * @return 删除后的链表头节点
     */
    static Node Delete(Node headNode, int position) {
        if(headNode == null) return null;
        int size = ListLength(headNode);
        if(position > size-1||position < 0) {
            System.out.println("Position of node to delete is invalid. The valid inputs are 0 to "+(size-1));
            return headNode;
        }
        Node lastNode = getLastNode(headNode);
        //删除表头
        if(position == 0) {
            if(lastNode!=null) {
                lastNode.next = headNode.next;
                return headNode.next;
            }else return null;
        }
        //删除中间或结尾节点
        else {
            Node previousNode = headNode;
            int count = 0 ;
            //获得目标节点的上一个节点
            while(count < position-1) {
                previousNode = previousNode.next;
                count++;
            }
            //要删除目标节点
            Node currentNode = previousNode.next;
            previousNode.next = currentNode.next;
        }
        return headNode;
    }


}
